The present invention generally relates to a system and method for stably identifying and characterizing isolated data patterns, or transients in a signal, representing some physical entity and more specifically to situations where the transients may be arbitrarily aligned with the sample points arising from an analog to digital (A/D) process applied to the signal.
In general, when a sampled digital signal from an A/D process is operated on by a signal processing function such as correlation, convolution, or transform, an arbitrary shift in the input signal with respect to the sample points causes changes in the output of the signal processing function, as well. This effect is aggravated when the sampling rate is reduced close to the critical sampling rate. FIG. 1 illustrates an arbitrary shift in the sampling of a signal. For many digital signal processes, such shifts produce a significant change in the output of the signal processing function. For example, the discrete Fourier transform computes inner products of time data and a complex exponential. If a signal is sampled and then resampled at the same rate but in such a manner that the second set of samples does not line up with the first, then the real, imaginary, and phase spectra will be different.
This variation in the end result arising from an arbitrary shift in the sample points on the signal is referred to herein as shift variance. In the case of the Discrete Fourier Transform, shift variance is not generally a problem because the commonly used magnitude spectrum is not shift variant.
For certain processes, shift variance can be aggravated where sampling is sparse on certain scales. An example is the affine discrete (especially critically sampled) wavelet transform. FIG. 2 shows a transient (FIG. 2a) and its wavelet decomposition (FIGS. 2b, 2c and 2d) before and after a shift (FIGS. 2e, 2f, 2g, 2h). The decomposition is totally different because of a shift of just one sample.
Thus, though the continuous form of the wavelet transform is shift invariant, the discrete form is not. FIG. 2 illustrates that the discrete wavelet transform is sensitive to the exact positioning of the transient in a sampled time record. Note that dramatically different coefficients results depending on where the transient happens to occur in the sampled time record. For physical signals, the location of the transient in the sampled time record is usually unknown and completely arbitrary. Thus, for physical signals the discrete wavelet transform (used in digital signal processing) is unreliable in its ability to detect, characterize and classify transients. This is unfortunate because as a continuous transform (unrealizeable in practice), the wavelet is unsurpassed in its ability to identify and characterize transients.
The shift variance problem for processes such as the discrete wavelet transform will now be discussed in more detail. For some processes, a shift of an integer number of samples of the input signal produces the same, albeit shifted, output which is usually acceptable. However, whenever the shift is a non-integer number of samples, the coefficients generally will be different (i.e., not simply shifted). The shift variance problem is aggravated in multiscale analysis such as the discrete wavelet transform because even an integer sample shift on the most resolute scale is a non-integer shift on less resolute scales.
Conventional attempts to overcome the shift variance problem are generally inadequate and typically rely on either oversampling, or resampling the data pattern based on zero crossings or maxima locations. Such conventional approaches are discussed in greater detail in the following paragraphs. There also exist specialized transforms designed to be immune to particular types of shifts, but these transforms are flawed due to their lack of generality and thus shall not be discussed further.
Oversampling reduces the sampling interval so that the extent of arbitrary shifting is confined. For example, if the original sampling rate were 1 KHz, the worst case subsample positional shift would be 0.5 msec in the time record. If the sampling rate were increased to 10 KHz, the worse case would be 0.05 msec. However, such improvement is achieved at the expense of the need to process a much greater amount of data. Note that the oversampling approach makes no attempt to solve the underlying problem. Rather, the oversampling approach simply bounds the error. Oversampling can be implemented in hardware by increasing the rate of the analog-to-digital converter, or in software by interpolation (such as upsampling with zeroes followed by low pass filtering). In either case, the cost to achieve oversampling is significant. In summary, oversampling is flawed because it does not optimally solve the shift variance problem, it greatly increases the burden of computation and it is expensive.
The flaws associated with oversampling are aggravated for methods, such as the discrete wavelet transform, which analyze signals on multiple scales. Wavelets are defined as the sets of functions: ##EQU1## The sets are formed by dilations, a, and translations, b, of a function g(x), called the analyzing wavelet. The set of functions maintains the shape of the analyzing wavelet throughout the time-frequency or time-scale plane.
The discrete wavelet transform of a signal s(x) can be represented by: ##EQU2## which is essentially an inner product of the discrete form of the conjugate of the wavelet, g(.), with the discrete form of the signal, s(.), where T is the sampling interval (T=1/f.sub.s). By varying the dilation, a, the transform provides decomposition at many scales. By analogy to map-making, "scale" is the level of detail provided at dilation a. Various conditions are usually imposed on wavelets, namely, the analyzing wavelet must have finite energy, and the integral of the wavelet must vanish.
Two currently employed approaches proposed specifically for solving the shift variance problem of the discrete wavelet transform will now be described. The first approach estimates the positions of the zero crossings in the record, then resamples the data in software in order to stabilize the samples. While this approach is an improvement over prior art, it experiences the following difficulties: (a) forming the resampled representation and reconstruction is very mathematically intensive; (b) it cannot be used with scale-envelopes because envelopes do not have zero-crossings; (c) it is designed for shift-correcting global patterns and thus is of questionable applicability for isolated transients and other isolated patterns; (d) it does not always produce a unique representation and reconstruction.
The second approach is a variation of the first method. Instead of using zero-crossings, the second approach uses signal maxima as the basis for resampling. The second approach is an improvement upon the first approach, but is still mathematically intensive, of questionable applicability for isolated patterns, and does not guarantee uniqueness.